package com.alexd.leetcode.contest.week102;


/*907. 子数组的最小值之和
用户通过次数 7
用户尝试次数 82
通过次数 7
提交次数 190
题目难度 Medium
给定一个整数数组 A，找到 min(B) 的总和，其中 B 的范围为 A 的每个（连续）子数组。

由于答案可能很大，因此返回答案模 10^9 + 7。

 

示例：

输入：[3,1,2,4]
输出：17
解释：
子数组为 [3]，[1]，[2]，[4]，[3,1]，[1,2]，[2,4]，[3,1,2]，[1,2,4]，[3,1,2,4]。 
最小值为 3，1，2，4，1，1，2，1，1，1，和为 17。
 

提示：

1 <= A <= 30000
1 <= A[i] <= 30000
*/
public class Solution3 {

	public int sumSubarrayMins(int[] A) {
		long res = 0;
		
		for (int len = A.length; len > 0; len--) {
			int step = A.length - len;
			for (int i = 0; i < len; i++) {
				if(step != 0) {
					A[i] = Math.min(A[i], A[i+1]);
				}
				res += A[i];
			}
		}
		return (int)(res % (Math.pow(10, 9) + 7));

        
    }
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] data = {3,1,2,4};
		System.out.println(new Solution3().sumSubarrayMins(data));
	}

}
